1. Field of the Invention
The present invention relates generally to systems and methods for generating solutions to global optimization problems. More particularly, the present invention relates to systems and methods for finding improved solutions to mixed integer problems through improving the identification of sets of conflicting constraints in a mixed integer program.
2. Brief Summary of the Invention
Mixed Integer Programming is a versatile, widely used technique for solving a variety of practical optimization problems. Generally, a mixed integer program (“MIP”) is an optimization problem of the form:                minimize f(x)        subject to G(x)=b                    l≦x≦u                        some or all xj integral,where x is a vector of variables, l and u are vectors of bounds, f(x) is an objective expression, and G(x)=b is a set of constraint expressions. While the above model has a minimization objective, one of skill will recognize that models may have maximization objectives.        
The simplest and most widely used form of MIP model is the Mixed Integer Linear Program (MILP):                minimize cTx        subject to Ax=b                    l≦x≦u                        some or all xj integral,where A is an m by n matrix, called the constraint matrix, and c is the linear objective vector. Thus, as one of ordinary skill in the art would recognize, a MILP is a linear program (“LP”) with an integrality restriction on some or all of the variables. Other forms of MIP model include the Mixed Integer Quadratic Program (MIQP), Mixed Integer Quadratically Constrained Program (MIQCP), and Mixed Integer Non Linear Program (MINLP).        
While the integrality restriction makes MIPs difficult to solve (both in general terms, and NP-hard in the technical sense), this restriction also makes the mixed-integer modeling paradigm a powerful tool in representing real-world business applications. In many situations, the solution to a MIP can yield a cost or benefit (for example, in dollars or other units) of pursuing a certain course of business. In a situation wherein the MIP solution yields a cost in dollars, the optimal solution might be one wherein the dollar cost is minimized. In a situation wherein the MIP solution yields the number of linear-feet of lumber that can be harvested from a forest, the optimal solution might be a solution wherein the number of linear-feet is maximized.
While absolute optimal solutions can and have been found for some MIPS (e.g., some MIPs with a small number of variables (n) or constraints (m)), for many MIPS, only solutions that are not provably optimal have been found. These solutions are often referred to as “best known” or “best objective” solutions. Such best known solutions still provide significant practical value in many situations. In these cases, it is often desirable to find the best known solution using the least amount of resources. For still other MIPs, no solution has yet been found.
(As used herein, “resources” can refer to money, time (seconds, minutes, hours, days, weeks, etc.), computer processor cycles, man-hours, or any other resource of which further depletion might theoretically yield a better solution. As also used herein, “optimize” means to improve the result, regardless of whether such improvement results in the absolute optimal result.)
With unlimited resources it might be possible to find one or more provably optimal or best objective solutions to any MIP. However, within the bounds of practicality, available resources are often limited. For example, the MIP solution might yield the distance and roads taken for the shortest road route between Lakeside, Ariz. and New York, N.Y. If this solution is being generated by a business interest, for a person using an internet mapping service, the limiting resource might be a time limitation of ten seconds. If forced to wait longer than ten seconds for a solution, the person might become frustrated and request a solution from a competitor. In this example, it would be desirable to find a best known solution with a resource limitation of ten seconds. However, without the resource limitation, it might be possible to find a provably optimal solution by considering every road leaving Lakeside, Ariz., every connecting road, and so on. Yet, the provably optimal solution might be less valuable if not delivered within the appropriate resource limitation.
In another example, the MIP solution might yield the cost in dollars of deploying each of 10,000 employees, having diverse skill sets, to perform certain tasks for a company. It might be desirable to determine the least costly manner to deploy the employees. Without any resource limitation, it might be possible to find a provably optimal solution by considering every possible deployment of every employee. Yet, the provably optimal solution might be less valuable if not delivered within an appropriate resource limitation. That is, the cost of exceeding the resource limitation might exceed the cost savings realized by finding a provably optimal solution.
Other examples of optimality problems addressed by MIPs include optimization of supply chain configurations (see U.S. Patent Application Publication Serial No. US 2002/0156663 A1, dated Oct. 24, 2002), loading patterns for a nuclear reactor core (see U.S. Patent Application Publication Serial No. US 2004/0196946 A1, dated Oct. 7, 2004), supply channel and contract modeling (see U.S. Patent Application Publication Serial No. US 2004/0172321 A1, dated Sep. 2, 2004), airline crew pairing (see “Recent Advances in Crew-Pairing Optimization at American Airlines,” by Ranga Anbil et al.), airline scheduling and ticket sales, and many other complex problems.
Before MIP solving techniques can be applied to a problem, a mathematical model of the MIP must be formulated. The mathematical model may consist of continuous decision variables, integer decision variables, or constraints, or a combination of some or all of these. Additionally, unless the objective function is zero, at least one objective function must be formulated. For example, the objective function for a business might define an objective of maximizing profits, maximizing revenue, minimizing costs, maximizing the number of employees, minimizing the number of employees, or some combination of these or other goals. An airline might define an objective of minimizing the number of empty seats on a flight while maximizing ticket sale revenue.
Errors in the formulation of the MIP and the objective function may lead to infeasible models. A simple example of such an infeasible model is described in the following paragraph.
An electrical generation company might devise a model for generating power with two power plants, each plant having five generators. In that model, among other constraints, the company might require that each plant have a minimum of three generators active at all times, that each plant have one generator inactive for use as an emergency backup at all times, that each plant have one generator inactive for maintenance at all times, and that each generator must be maintained in an inactive state at least once per week. The company might formulate a further constraint to maximize profit by limiting electrical generation through requiring that at least five generators remain inactive at all times. In this example, it is simple to see that the where the company has ten total generators, the requirements of five inactive generators and six active generators (three per plant for each of two plants) cannot be met simultaneously. Thus, it is easy to determine that this model is infeasible.
However, in models involving tens, hundreds, thousands, or ten thousands of variables or constraints, making an infeasibility determination may be much more difficult. In such models, a known approach to finding errors leading to infeasibility is to reduce the infeasibility to a relatively small set of constraints. This approach is routinely employed for continuous models. However, due to the prohibitive resource cost of identifying sets of conflicting constraints in integer or mixed integer problems, this approach is not regularly applied to such problems.
It would be desirable to provide improved methods and systems for determining whether MIP models are infeasible. It would further be desirable to provide less costly methods and systems for identifying relatively small sets of constraints that make MIP models infeasible.
Further, while it is known and desirable to one of ordinary skill to create feasible models, applicants are not aware of suggestions by others to improve upon the objective function by deliberately creating infeasibilities in a model.
Accordingly, it would be desirable to provide methods and systems for deliberately attempting to create one or more infeasibilities in a model in an effort to improve upon the objective function. It is further desirable to provide methods and systems for identifying relatively small sets of constraints that may be limiting an objective function, in order that the modeler may consider whether such constraints may or should be changed to improve the overall result of the model.
In the context of MIPs, a conflict is a set of mutually contradictory constraints and bounds within a model that renders the MIP infeasible. A minimal conflict is such a conflict that is minimal in that removal of any single constraint within the set will eliminate the infeasibility in the set. Removal of this single constraint may or may not render the entire model feasible.
In linear programs (LP), minimal conflicts are known as irreducibly inconsistent sets (IIS). Detection of an IIS among the constraints of a model involves standard methodology known in the field. For example, some techniques for IIS detection are described in an article by John Gleeson and Jennifer Ryan, titled “Identifying Minimally Infeasible Subsystems of Inequalities.” Further, an IIS finder has been included in software sold by Ilog, Inc. of Mountain View, Calif., under the name ILOG CPLEX. However, a conflict in terms of MIPs is more general than just IIS. IIS is understood to be strictly related to continuous LP models, while conflicts of the type discussed herein may include mixed integer models or models containing quadratic elements. Thus, application of IIS detection to MIPs is made through the relaxation of MIP integrality restrictions by which a LP is derived.
If a model contains only one conflict, removal of the lone conflict results in feasibility. Whereas, if the model contains multiple conflicts, removal of a single conflict will not result in feasibility. For example, the simplified generator example above contains only one explicit conflict which happens to be a minimal conflict. In that model, removal of either the three generators active per plant constraint or the five generators inactive constraint would eliminate the explicit infeasibility in the model. In another example, a model may contain the following set of constraints:                y>x+1        z>y+1        a>z+1        x>a+1Again, in this example, it is easy to determine that a conflict exists, rendering the model infeasible. It is also easy to determine that this set of constraints contains a minimal conflict. Removal of any of the four constraints would allow a feasible solution.        
However, in more complex models it may be very difficult to quickly determine that one or more conflicts exists. Where resources are limited, it may be impossible to determine that conflicts exist in any complex model.
Many scheduling and routing models are too difficult for mathematics. To be more precise, mathematical programming (MP) techniques based on linear algebra (the most common technique for optimization of schedules and plans) break down on most large routing and detailed scheduling problems.
For such situations, a second optimization technology called constraint programming (CP), aimed at solving difficult scheduling and routing problems, was developed. Constraint programming is an emergent software technology for declarative description and effective solving of large, particularly combinatorial, problems usually in the areas of planning and scheduling. Although math is used to help find the correct search path among many choices, CP is not fundamentally based on advanced mathematics. CP is based primarily on computer science-logic programming, graph theory and artificial intelligence efforts.
CP's approach to optimization is different from MP. CP finds efficient solutions (feasible combinations of resource assignments and activities with good utilization) in problems with too many individual constraints regarding sequence and timing for MP. CP is useful when dealing with the complexity of many real problems. For example, CP is useful for scheduling people, machines, or process steps; dispatching trucks delivering freight; and dispatching technicians installing cable service, where the operating constraints and business rules are too complex for mathematics.
CP systematically eliminates possible solutions in order to rapidly identify feasible solutions that can be optimized. Thus, CP allows direct modeling of complex problems (e.g., scheduling or routing), where MP requires a linearization of the problem.
As with MP, a CP model is expressed in a declarative fashion, using decision variables, constraints and objectives. CP's methodology of modeling revolves around formalizing a problem description. For example, to schedule a large number of resources and activities that respect capacity limitations, sequencing requirements, synchronization and individual delivery time commitments, CP would require steps including: defining activities with information about execution time, sub-activities, resource requirements, alternative resources allowed, precedence requirements, costs, etc.; defining resources that have capacities, costs and capabilities that can be required, consumed or shared by certain activities, and produced by others; balancing sometime conflicting business goals; tracking resource utilization, consumption and available capacity; tracking time to be able to sequence activities and respect time windows when activities must occur; controlling the possible values for each decision variable; and reducing the possible values for a decision variable as other variables are determined.
In this example, three concepts are fundamental to the way constraint programming generates workable schedules from such a model. The first concept is the manner in which CP handles time. MP can divide time into buckets and decide what is optimal for each bucket. However, MP can be less adequate when computing the optimal sequence of large numbers of inter-related activities with a start time for each. CP, for example, can determine the best sequence of activities that satisfy capacity limitations, set-up times, maintenance requirements, availability restrictions, and individual delivery due dates. The second major concept offered by CP is domain reduction. Domain reduction is the internal mechanism that makes difficult scheduling problems manageable (i.e., every resource or activity to be scheduled has a certain number of possible values that can be systematically reduced until a solution is reached). Every domain reduction makes the problem easier. Reducing the size of the search space is a concept found in both MP and CP, but each goes about it differently. CP has fewer limitations than MP on its ability to work with non-linear constraints. The third concept relates to the second: CP incorporates the notion of systematically exploring a decision tree for feasible and efficient solutions. One benefit of this structured approach is the ability to move flexibly throughout the search space and to backtrack when early choices turn out to be dead-ends.
(Constraint Programming is used in software sold by ILOG, Inc. of Mountain View, Calif. under the name ILOG Constraint Programming.)
In constraint programming, conflicts (either minimal or non-minimal) are known as “explanations.”
In many cases, constraints are used actively to reduce domains by filtering values that cannot take part in any solution. This process is called constraint propagation, domain filtering, pruning, or consistency technique. Constraint propagation may be used to fully solve problems. However, this is rarely done due to efficiency issues. It is more common to combine an efficient albeit incomplete consistency technique with non-deterministic search. This consistency technique does not remove all inconsistent values from the domain of constraint variables. Yet, the technique can eliminate many obvious inconsistencies, thereby simplifying the problem and reducing the search space.
Many theoretical consistency techniques are known, including: node consistency, arc consistency (including AC-1, AC-2, AC-3, AC-4, AC-5, AC-6, and AC-7 algorithms), path consistency, restricted path consistency, k-consistency, (i,j)-consistency, inverse consistency, and singleton consistency. Overviews of these and other techniques are briefly described by Roman Bartak in an article titled, “Theory and Practice of Constraint Propagation.”
With respect to MIP (including LP), the equivalent of constraint propagation is called “bound strengthening” (BS). A simple example of BS is found in the following example. Assume a problem with variables x and y. Both variables have zero as lower bound and no upper bound. The problem includes a constraint x+2y=1. From this information, one can infer that x must have an upper bound of l and y must have an upper bound of ½. By making this inference, the defined bounds of infinity on both x and y have been strengthened. In a variation of this example, if y is defined as an integer variable, y could be rounded down to 0, as the upper bound (i.e., ½) is non-integer. In this manner, bound strengthening accounts for integrality constraints.
Strengthened bounds on a subset of variables may allow strengthened bounds on other variables. In this example, if the upper bound of x is strengthened to ½, the lower bound of y must be strengthened from zero to ¼, to satisfy the constraint x+2y=1. This type of bound strengthening process may result in very long sequences of minute bound tightenings. Thus, the process is often interrupted when some resource limit is reached. An interruption of this type may cause non-monotonicity in the infeasibility detection.
Infeasibility may be detected through BS when the lower bound of a variable is tightened to a larger value than its upper bound.
Presolve techniques transform a MIP into an equivalent MIP that is easier to solve. When a problem has been presolved, one can easily generate a solution to the original MIP from a solution of the presolved MIP. BS is often employed as part of presolve. A discussion of several known presolve methods is set forth by Jacek Gondzio in an article titled, “Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method.” Gondzio explains that it has been known, almost since the first applications of LP, that presolve analysis of the problem before passing it to a solver often reduces solution time considerably. Accordingly, it is understood that one of ordinary skill in the art will be familiar with presolve techniques.
Ulrich Junker of Ilog, S.A., teaches an algorithm named QuickXplain in an article titled, “QuickXplain: Conflict Detection for Arbitrary Constraint Propagation Algorithms.” Junker explains that at the time of his article, existing conflict detection methods for constraint satisfaction problems (CSPs) could not make use of powerful propagation, which made them unusable for complex real-world problems. Likewise, Junker explained that powerful constrain propagation methods lacked the ability to extract dependencies or conflicts. Accordingly, Junker proposed QuickXplain to overcome such problems by recursively partitioning the problem into subproblems of half the size and immediately skipping the subproblems that do not contain an element of the conflict.
Junker distinguishes propagation-specific conflicts from global conflicts, noting that not each global conflict is propagation-specific. Junker teaches that it is possible to detect conflicts a posteriori for any constraint propagation algorithm as complex as it may be. Given a set of inconsistent constraints, the basic idea is to iteratively test the consistency of subsets of the given constraints until a minimal conflict is found. Junker notes that the existing conflict detection methods need O(n·k) consistency tests to find a minimal conflict of size k out of n constraints. Junker teaches an improvement over such methods by recursively partitioning the conflict detection problem into subproblems of half the size and immediately skipping those subproblems that do not contain an element of the conflict. QuickXplain needs O(n·log(k+1)+k2) consistency tests. Thus, QuickXplain is more efficient if k is small compared to n.
In illustrating QuickXplain, Junker proposes the following simple example, which contains a conflict that is easy to detect. Suppose a customer wants to buy a station wagon with the following extras: 1. metal color, 2. ABS, 3. roof racks, 4. one additional seat, 5. special luxury version. Suppose that those extras cost c1:=$500, c2:=$500, c3:=$500, c4:=$800, and c5:=$2600. Suppose that the customer cannot exceed $3000 for the extras. The example is modeled with a constrained integer variable xiε{0,1} for each extra i:=1, . . . , 5, a variable yε[0,3000] for the costs of the extras, and the following constraint:
  y  =            ∑              i        =        1            5        ⁢                  c        i            ·              x        i            The customer requests are modeled by the constraints xi=1 for each i=1, . . . , 5.
Junker explains that existing algorithms could return a conflict explanation of the form X:={p1, p2, p3, p4, p5}. However X is not a minimal conflict. If p5 is chosen, no other extra can be chosen without violating the $3000 budget. Thus, the example contains four possible minimal conflicts {p1,p5}, {p2, p5}, {p3,p5}, and {p4,p5}, which are significantly smaller than X.
QuickXplain finds minimal conflicts by first adding the given constraints p1, . . . , p5 in a given order to a constraint propagation engine until a failure state is obtained. In the example, the first failure occurs after p5 is added. Consequently, p5 belongs to some minimal conflict. After obtaining a failure, the propagation engine backtracks to the initial state and adds p5 again. Because adding p5 does not result in a failure, the remaining constraints p1, . . . ,p4 are added one at a time until a failure occurs. Addition of the first constraint, p1, immediately causes a failure because $2600+$500>$3000. Thus, a minimal conflict {p1,p5} is found.
Junker considers a slightly more complex variant of the example. It includes eight requests for extras p1, . . . , p8 with costs c1=c3=c4=c6=$100 and c2=c5=c7=c8=$800. The scalar product is adapted to correspond to these requests and costs, but the budget remains $3000. The existing algorithm needed 26 steps to determine a minimal conflict. While QuickXplain needs only 21 steps.
In this example, QuickXplain begins by adding the constraints iteratively until the first element of the conflict is detected on addition of p8 (8 steps). The problem is then decomposed into two subproblems. The first subproblem consists of finding a conflict among {p5, . . . , p7} while keeping {p1, . . . , p4} and the already detected elements of the conflict in the background as hard constraints. In this example, p8 is initially kept in the background with the first half of the constraints {p1, . . . , p4}. To set up this first subproblem, Junker explains that QuickXplain backtracks three steps and re-adds the already detected element of the conflict (i.e., p8) to the background (1 step). QuickXplain then reads the constraints {p5, . . . , p7} until a failure is detected on addition of p7 (3 steps). QuickXplain again backtracks and re-adds the already detected elements of the conflict (i.e., p7 and p8) to the background (1 step). QuickXplain then reads the constraints {p5, . . . , p6} until a failure is detected on addition of p5 (1 step). QuickXplain again backtracks and re-adds the already detected elements of the conflict (i.e., p5, p7 and p8) to the background (1 step). QuickXplain obtains a failure at this point. Thus, QuickXplain has detected three elements of the conflict, i.e., p5, p7 and p8. At this point, QuickXplain sets up the second subproblem. QuickXplain backtracks to the beginning and re-adds all of the detected elements of the conflict (3 steps). QuickXplain then adds the original background constraints from the first half of the problem {p1, . . . , p4} until a failure is detected on addition of p2 (2 steps). QuickXplain again backtracks and re-adds the already detected elements of the conflict (i.e., p2) to the background (i.e., p5, p7 and p8) (1 step). QuickXplain obtains a failure at this point. In this manner, QuickXplain detects the first (and, in this example, only) minimal conflict.
Junker explains that QuickXplain can be supplied with a CSP (C,U) in explainable form and determine a conflict for it if Π(C∪U) contains an inconsistency ⊥. Otherwise, QuickXplain throws an exception indicating that there is no conflict. QuickXplain consists of an exploration phase in which the unexplored constraints in U are step-by-step added to C by using the function add of the underlying constraint propagation engine. Junker lets α1, . . . , αn be the order in which the constraints are added. The first αk that causes a failure when added to C belongs to a minimal Π-conflict. Thus, that αk is added to X and its addition to C is undone. With this background, Junker provides an algorithm for QuickXplain:
Algorithm QUICKXPLAIN(C, U)1.if ⊥ ∈ C then return ∅;2.if U = ∅ then throw exception ‘no conflict’;3.let α1,...,αn be an enumeration of U;4.k := 0;5.while ⊥ ∉ C and k < n do6.  Ck := C;7.  k := k + 1;8.  C := Π(C ∪ {αk});9.if ⊥ ∉ C then throw exception ‘no conflict’;10.X := {αk};11.let i be split(k − 1);12.U1 := {α1,...,αi};13.U2 := {αi+1,...,αk−1};14.if U2 ≠ ∅ then15.  C := Ci;16.  C := Π(C ∪ X);17.  let Δ2 be the result of QUICKXPLAIN(C, U2);18.  X := Δ2 ∪ X;19.if U1 ≠ ∅ then20.  C := C0;21.  C := Π(C ∪ X);22.  let Δ1 be the result of QUICKXPLAIN(C, U1);23.  X := Δ1 ∪ X;24.return X.In this algorithm, when an element αk of X is detected, the remaining constraints are divided into two disjoint subsets U1:={α1, . . . , αi} and U2:={αi+1, . . . , αk−1} where i:=split(k−1). Usually, the split is in the middle and split(n):=n/2 is chosen. Then, the algorithm is recursively applied to find a conflict X2 among U2 using C∪U1 as the background and a conflict X1 among U1 using C∪U2 as the background. (As explained by Junker, the “background” contains the subset that is not currently being tested for conflicts and the already identified elements of the minimal conflict. Thus a “background” constraint may or may not be part of a conflict.) Then, the set X:=X1∪X2∪{αk} is a minimal Π-conflict for (C,U).
According to the algorithm, QuickXplain immediately skips a subproblem if the background of the subproblem is inconsistent. Thus, only subproblems containing elements of X will be explored. Hence, k subproblems will be explored in total. This leads to a maximum of n·log(k+1) add calls for exploration. To count the add calls needed for testing the elements of X, Junker looks at the depth of the recursive calls of QuickXplain. Each time a new element of X is detected, the call depth can be increased. Thus, the i-th element of X is detected at depth i or less. The algorithm tests twice when detected (at lines 16 and 21) and once at smaller depths (at line 21). Thus, the algorithm requires a maximum of                k        Σ(i+1)=(k+3)·k/2        i=1tests. (Junker notes that the QuickXplain algorithm is used as the explanation component of an advanced industrial constraint-based configuration tool sold by ILOG, Inc. of Mountain View, Calif. under the name ILOG Configurator.)        
Junker also proposes three extensions of QuickXplain. First, he proposes application of QuickXplain in each node of a (systematic and complete) backtrack search for a solution. If all sons of a node fail, use the hyperresolution principle as employed in ATMS in order to compute a conflict that no longer contains constraints added in the son nodes. These conflicts allow use of conflict-based backjumping or dynamic backtracking as the search method. Second, he proposes application of a (systematic and complete) backtrack search for a solution in each step of QuickXplain. Already detected solutions can be maintained internally and serve as starting points for some of the backtrack searches. They can also render some of the backtrack searches obsolete. Third, he proposes interleaving or nesting the first two extensions.
While, it is known and desirable to one of ordinary skill to use the above-described bound strengthening within QuickXplain to identify conflicts, applicants are not aware of suggestions by others to use presolve or complete MIP tree exploration methodology within QuickXplain or other prior art algorithms to test for conflicts in mixed integer programs.
Accordingly, it would be desirable to provide methods and systems for determining the existence of conflicts in models. It would further be desirable to provide methods and systems for identifying sets of constraints containing conflicts in models. It would further be desirable to provide methods and systems for determining the existence of minimal conflicts in models. It would be still further desirable to provide methods and systems for identifying sets of constraints containing minimal conflicts in models. It would be still further desirable to provide methods and systems for using presolve or complete MIP tree exploration methodology to determine the existence of or identify conflicts in models.